{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "b9b88ddd",
   "metadata": {},
   "source": [
    "### 贪心算法"
   ]
  },
  {
   "cell_type": "raw",
   "id": "a7be8087",
   "metadata": {},
   "source": [
    "所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。\n",
    "也就是说，不从整体最优上加以考虑，它所做出的仅仅是在某种意义上的局部最优解。\n",
    "\n",
    "贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。\n",
    "必须注意的是，贪心算法不是对所有问题都能得到整体最优解，\n",
    "选择的贪心策略必须具备无后效性（即某个状态以后的过程不会影响以前的状态，只与当前状态有关。）\n",
    "\n",
    "所以，对所采用的贪心策略一定要仔细分析其是否满足无后效性。"
   ]
  },
  {
   "cell_type": "raw",
   "id": "7f423195",
   "metadata": {},
   "source": [
    "有1元、5元、10元、50元、100元、500元的硬币，数量自定义\n",
    "现在要用这些硬币来支付 A A A 元，最少需要多少枚硬币？"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0df4c4db",
   "metadata": {},
   "outputs": [],
   "source": [
    "v = [1, 5, 10, 50, 100, 500]\n",
    "count = list(map(int, input().split()))\n",
    "A = int(input())\n",
    "\n",
    "result = list()\n",
    "for i in range(5, -1, -1):\n",
    "    num = A // v[i]\n",
    "    if num <= count[i]:\n",
    "        result.append(num)\n",
    "        A -= v[i] * num\n",
    "    else:\n",
    "        result.append(count[i])\n",
    "        A -= v[i] * count[i]\n",
    "\n",
    "print(*result[::-1],sep=',')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "03c6e1c0",
   "metadata": {},
   "source": [
    "### 字典序最小单词"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1c5000ca",
   "metadata": {},
   "outputs": [],
   "source": [
    "问题描述\n",
    "\n",
    "给定一个单词，请问在单词中删除 t 个字母后，能得到的字典序最小的单词是什么？\n",
    "\n",
    "输入格式\n",
    "\n",
    "输入的第一行包含一个单词，由大写英文字母组成。\n",
    "第二行包含一个正整数 t。\n",
    "\n",
    "输出格式\n",
    "\n",
    "输出一个单词，表示答案\n",
    "\n",
    "样例输入\n",
    "\n",
    "LANQIAO\n",
    "3\n",
    "\n",
    "样例输出\n",
    "\n",
    "AIAO"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8e744aa4",
   "metadata": {},
   "source": [
    "### 二分搜索"
   ]
  },
  {
   "cell_type": "raw",
   "id": "8e690772",
   "metadata": {},
   "source": [
    "二分搜索只适用于单调上升序列。以下假设数组nums不为空"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e122c378",
   "metadata": {},
   "outputs": [],
   "source": [
    "如果是无序数组，从第0个位置开始遍历搜索，平均时间复杂度：O(n) # 普通\n",
    "如果是有序数组，可以使用二分搜索，最坏时间复杂度为O(log2 n)     # 二分"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "235347c5",
   "metadata": {},
   "outputs": [],
   "source": [
    "假设在[begin，end）范围内搜索某个元素 v，mid == （begin + end）/ 2\n",
    "①、如果v < m，去[begin ， mid）范围内二分搜索\n",
    "②、如果v > m，去[mid + 1， end）范围内二分搜索\n",
    "③、如果v == m ，直接返回 mid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9e25dc1c",
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "def binarySearch(nums, target):\n",
    "    begin = 0\n",
    "    end = len(nums)\n",
    "\n",
    "    while begin < end:\n",
    "        mid = (begin + end) // 2\n",
    "        \n",
    "        if target < nums[mid]:\n",
    "            end = mid - 1\n",
    "        elif target > nums[mid]:\n",
    "            begin = mid + 1\n",
    "        elif target == nums[mid]:\n",
    "            return mid\n",
    "\n",
    "    return False\n",
    "\n",
    "l = list(map(int, input().split()))\n",
    "\n",
    "print(binarySearch(l, 5))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b022664f",
   "metadata": {},
   "source": [
    "### 寻找左侧边界的二分搜索"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "11cc5e8f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def left_bound(nums, target):\n",
    "    begin = 0\n",
    "    end = len(nums)\n",
    "\n",
    "    while begin < end:\n",
    "        \n",
    "        mid = (begin + end) // 2\n",
    "        \n",
    "        if target < nums[mid]:\n",
    "            end = mid\n",
    "        elif target > nums[mid]:\n",
    "            begin = mid+1\n",
    "        elif target == nums[mid]:\n",
    "            end = mid\n",
    "\n",
    "    return begin\n",
    "\n",
    "l = list(map(int, input().split()))\n",
    "\n",
    "print(left_bound(l, 5))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "990d14d8",
   "metadata": {},
   "source": [
    "### 寻找右侧边界的二分搜索"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0a6e918d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def right_bound(nums, target):\n",
    "    begin = 0\n",
    "    end = len(nums)\n",
    "\n",
    "    while begin < end:\n",
    "        \n",
    "        mid = (begin + end) // 2\n",
    "        \n",
    "        if target < nums[mid]:\n",
    "            end = mid \n",
    "        elif target > nums[mid]:\n",
    "            begin = mid + 1\n",
    "        elif target == nums[mid]:\n",
    "            end = mid + 1\n",
    "\n",
    "    return begin - 1\n",
    "\n",
    "l = list(map(int, input().split()))\n",
    "\n",
    "print(right_bound(l, 5))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "75ec289f",
   "metadata": {},
   "source": [
    "### 回溯算法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d9dc5f41",
   "metadata": {},
   "outputs": [],
   "source": [
    "result = []\n",
    "def backtrack(路径, 选择列表):\n",
    "    if 满足结束条件:\n",
    "        result.add(路径)\n",
    "        return\n",
    "    \n",
    "    for 选择 in 选择列表:\n",
    "        做选择\n",
    "        backtrack(路径, 选择列表)\n",
    "        撤销选择"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "66199f9e",
   "metadata": {},
   "source": [
    "### 全排列"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1e6780c7",
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import product\n",
    "\n",
    "print(list(product([1, 2, 3], [3, 4, 5])))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "00e3aef0",
   "metadata": {},
   "source": [
    "### N皇后问题"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "872a9190",
   "metadata": {},
   "outputs": [],
   "source": [
    "棋盘中皇后可以攻击同一行、同一列，或者左上、左下、右上、右下四个方向的任意单位。\n",
    "现在有一个 N × N × N × N 的棋盘，放置 N 个皇后，使得它们不能互相攻击，返回所有可能的结果。\n",
    "\n",
    "棋盘中的某一格未放置皇后时用 '.' 表示，放置皇后用 'Q' 表示，一个 4 × 4 × 4×4 的空棋盘的表示方式如下："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e29fced2",
   "metadata": {},
   "outputs": [],
   "source": [
    "pots = [[0]* 4 for i in range(4)]\n",
    "\n",
    "print(*pots,sep='\\n')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e07fb8d3",
   "metadata": {},
   "outputs": [],
   "source": [
    "# board中小于row的那些行都已经成功的放置了皇后\n",
    "# 第row行的所有列都是放置皇后的选择\n",
    "# 当row=n时，说明棋盘已经放满了(棋盘最后一行的索引是n-1)\n",
    "def backtrack(board, row):\n",
    "    if row == len(board):\n",
    "        res.append(board[:])  # 浅拷贝\n",
    "\n",
    "    n = len(board)\n",
    "    for col in range(n):\n",
    "        if not isValid(board, row, col):\n",
    "            # 当这样放置皇后不合法时跳过，isValid的具体内容后面会提到\n",
    "            continue\n",
    "\n",
    "        # 将board[row][col]这一格放置皇后\n",
    "        board[row] = board[row][:col] + 'Q' + board[row][col+1:]\n",
    "\n",
    "        backtrack(board, row + 1)\n",
    "\n",
    "        # 撤销选择\n",
    "        board[row] = board[row][:col] + '.' + board[row][col+1:]\n",
    "        \n",
    "def isValid(board, row, col):\n",
    "    \"\"\"\n",
    "    判断是否可以在board[row][col]位置处放置皇后\n",
    "    \"\"\"\n",
    "    n = len(board)\n",
    "\n",
    "    # 检查列中是否有皇后相互冲突\n",
    "    for i in range(row):\n",
    "        if board[i][col] == 'Q':\n",
    "            return False\n",
    "\n",
    "    # 检查右上方是否有皇后相互冲突\n",
    "    for (i, j) in zip(range(row - 1, -1, -1), range(col + 1, n)):\n",
    "        if board[i][j] == 'Q':\n",
    "            return False\n",
    "\n",
    "    # 检查左上方是否有皇后相互冲突\n",
    "    for (i, j) in zip(range(row - 1, -1, -1), range(col - 1, -1, -1)):\n",
    "        if board[i][j] == 'Q':\n",
    "            return False\n",
    "\n",
    "    # 之所以不需要考虑左下方和右下方，是因为皇后是逐行从上往下放置的\n",
    "\n",
    "    return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "088df717",
   "metadata": {},
   "source": [
    "### 子集"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c52b623f",
   "metadata": {},
   "outputs": [],
   "source": [
    "result = []\n",
    "def backtrack(路径, 选择列表):\n",
    "    if 满足结束条件:\n",
    "        result.add(路径)\n",
    "        return\n",
    "    \n",
    "    for 选择 in 选择列表:\n",
    "        做选择\n",
    "        backtrack(路径, 选择列表)\n",
    "        撤销选择"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f71ba00f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def backtrack(nums, start, track):\n",
    "    result.append(track[:])\n",
    "\n",
    "    for i in range(start, len(nums)):\n",
    "        track.append(nums[i])\n",
    "        backtrack(nums, i + 1, track)\n",
    "        track.pop()\n",
    "\n",
    "\n",
    "result = []\n",
    "track = []\n",
    "nums = [1, 2, 3]\n",
    "backtrack(nums, 0, track)\n",
    "print(result)\n",
    "# [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "009694cb",
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import combinations\n",
    "nums = [1, 2, 3]\n",
    "for i in range(1, len(nums)+1):\n",
    "    print(list(combinations(nums, i)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3d8ff1e4",
   "metadata": {},
   "source": [
    "### 组合"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "344ca7f4",
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import combinations\n",
    "\n",
    "l = list(range(1, 5))\n",
    "\n",
    "print(list(combinations(l,2)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e65f9579",
   "metadata": {},
   "source": [
    "### 排列"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "12889ca4",
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import permutations\n",
    "\n",
    "l = list(range(1, 5))\n",
    "\n",
    "print(list(permutations(l,2)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a28dad35",
   "metadata": {},
   "source": [
    "### 广度优先搜索"
   ]
  },
  {
   "cell_type": "raw",
   "id": "154bc037",
   "metadata": {},
   "source": [
    "BFS的核心思想不难理解，就是把一些问题抽象成图，从一个点开始，向四周扩散。\n",
    "\n",
    "一般来说，我们写BFS算法都是用\"队列\"这种数据结构，每次将一个节点周围的所有节点加入队列。\n",
    "\n",
    "BFS相对于DFS的最主要区别是：BFS找到的路径一定是最短的，但代价是空间复杂度比DFS大很多。\n",
    "\n",
    "BFS算法主要用于在一张图中找到从起点start到目标target的最近距离。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ec69adc5",
   "metadata": {},
   "outputs": [],
   "source": [
    "它是从初始结点开始,应用产生式规则和控制策略生成第一层结点,同时检查目标结点是否在这些生成的结点中。\n",
    "若没有,再用产生式规则将所有第一层结点逐一拓展,得到第二层结点,并逐一检査第二层结点是否包含目标结点。\n",
    "若没有,再用产生式规则拓展第二层结点。\n",
    "如此依次拓展,检査下去,直至发现目标结点为止。\n",
    "如果拓展完所有结点,都没有发现目标结点,则问题无解"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "5b13c12f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def BFS2(graph, end):\n",
    "    queue = list()\n",
    "    queue.append(end)\n",
    "    \n",
    "    seen = set()\n",
    "    seen.add(end)\n",
    "    \n",
    "    #记录一下父子节点这样方便求最短路\n",
    "    data = {end:None} \n",
    "    \n",
    "    while (len(queue) > 0):\n",
    "        parent_node = queue.pop(0)\n",
    "        nodes = graph[parent_node]\n",
    "        for node in nodes:\n",
    "            if node not in seen:\n",
    "                queue.append(node)\n",
    "                seen.add(node)\n",
    "                data[node] = parent_node           \n",
    "    return data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "aae7b83c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'g': None, 'e': 'g', 'b': 'e', 'd': 'e', 'f': 'e', 'a': 'b', 'c': 'd'}\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "\"start = 'a'\\nwhile start:\\n    \\n    print(start,end='->')\\n    \\n    start = parent[start]\\n\\n# print(parent)\\nprint('END')\""
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "graph = {\n",
    "    \"a\" : [\"b\",\"c\"],\n",
    "    \"b\" : [\"a\",\"e\"],\n",
    "    \"c\" : [\"a\",\"d\",\"f\"],\n",
    "    \"d\" : [\"c\",\"e\"],\n",
    "    \"e\" : [\"b\",\"d\",\"f\",\"g\"],\n",
    "    \"f\" : [\"c\",\"e\"],\n",
    "    \"g\" : [\"e\"]\n",
    "}\n",
    "\n",
    "parent = BFS2(graph, 'g')\n",
    "\n",
    "start = 'a'\n",
    "while start:\n",
    "    \n",
    "    print(start,end='->')\n",
    "    \n",
    "    start = parent[start]\n",
    "\n",
    "# print(parent)\n",
    "print('END')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "be47652f",
   "metadata": {},
   "source": [
    "### 二叉树的最小高度"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "19ad816a",
   "metadata": {},
   "source": [
    "### 动态规划"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8d2ef661",
   "metadata": {},
   "outputs": [],
   "source": [
    "最长递增子序列(Longest Increasing Subsequence)\n",
    "\n",
    "输入一个无序数组，找到其中最长递增子序列的长度。\n",
    "\n",
    "例如输入 nums = [10, 9, 2, 5, 3, 7, 10, 18] ，其中最长的递增子序列是 [2, 3, 7, 10] ，所以算法输出的应该是 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3d0d6f1c",
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "nums = list(map(int, input().split()))\n",
    "\n",
    "n = len(nums)\n",
    "\n",
    "dp = [1] * n\n",
    "\n",
    "for i in range(n):\n",
    "    for j in range(i):\n",
    "        if nums[i] > nums[j]:\n",
    "            dp[i] = max(dp[i], dp[j] + 1)\n",
    "\n",
    "print(max(dp))"
   ]
  },
  {
   "cell_type": "raw",
   "id": "ce429ddc",
   "metadata": {},
   "source": [
    "最长公共子序列(Longest Common Subsequence)\n",
    "输入 str1=“abcde”，str2=“aceb”，算法应该输出 3 ，因为它们的最长公共子序列是 “ace”，它的长度就是 3 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f4712c16",
   "metadata": {},
   "outputs": [],
   "source": [
    "str1 = \"abcd\"\n",
    "str2 = \"abcde\"\n",
    "\n",
    "m = len(str1)\n",
    "n = len(str2)\n",
    "    \n",
    "dp = [[0] * (n) for i in range(m)]\n",
    "\n",
    "# 最长公共子序列\n",
    "for i in range(m):\n",
    "    for j in range(n):\n",
    "        if str1[i] == str2[j]:\n",
    "            dp[i][j] = dp[i - 1][j - 1] + 1\n",
    "        else:\n",
    "            dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])\n",
    "\n",
    "print(*dp,sep=' ') \n",
    "print(dp[m-1][n-1]) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "79e6e8fe",
   "metadata": {},
   "outputs": [],
   "source": [
    "最长回文子序列\n",
    "\n",
    "输入一个字符串 s，找出 s 中的最长回文子序列长度。\n",
    "\n",
    "比如输入 s = “aecda”，算法返回 3，因为最长回文子序列是 “aca”，长度为 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "454a08d0",
   "metadata": {},
   "outputs": [],
   "source": [
    "string = 'aecda'\n",
    "\n",
    "n = len(string)\n",
    "dp = [[0] * n for i in range(n)]\n",
    "\n",
    "\n",
    "for i in range(n):\n",
    "    dp[i][i] = 1\n",
    "    for i in range(n - 2, -1, -1):\n",
    "        for j in range(i + 1, n):\n",
    "            if string[i] == string[j]:\n",
    "                dp[i][j] = dp[i + 1][j - 1] + 2\n",
    "            else:\n",
    "                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])\n",
    "    \n",
    "print(dp[0][n - 1]) "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "lanqiaobei",
   "language": "python",
   "name": "lanqiaobei"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
